﻿using System;
using System.Collections.Generic;
using System.Text;
using System.Linq;

namespace AlgorithmTest
{
    // T_[四个数字排序]_[算法名]
    public class T_0126_KthSmallest : IAlgorithm
    {
        // 二叉搜索树中第K小的元素

        // 给定一个二叉搜索树的根节点 root ，和一个整数 k ，请你设计一个算法查找其中第 k 个最小元素（从 1 开始计数）。

        // 提示：
        //  树中的节点数为 n 。
        //  1 <= k <= n <= 10^4
        //  0 <= Node.val <= 10^4

        // 进阶：如果二叉搜索树经常被修改（插入/删除操作）并且你需要频繁地查找第 k 小的值，你将如何优化算法？

        public void Test()
        {
            // 算法参数定义

            // 算法执行与打印
            //Console.WriteLine(KthSmallest());
        }


        int target = -1;
        int count;

        public int KthSmallest(TreeNode root, int k)
        {
            count = k;
            InOrderTraversal(root);
            return target;
        }

        public void InOrderTraversal(TreeNode node)
        {
            if (node == null)
                return;
            InOrderTraversal(node.left);
            if (--count == 0)
            {
                target = node.val;
                return;
            }
            InOrderTraversal(node.right);
        }
    }
}
